package July;

import com.sun.scenario.animation.shared.ClipEnvelope;

import java.util.Arrays;

/**
 * @author:gao
 * @date:2020/7/12
 * @time:9:27
 * @version:0.0.1
 * @description:none
 */

public class CaculateMinHP {
}

//暴力，超时
class Solution000001 {
    int min = Integer.MAX_VALUE;
    int[][] dungeon;
    int rows;
    int cols;
    public int calculateMinimumHP(int[][] dungeon) {
        this.dungeon = dungeon;
        rows = dungeon.length;
        cols = dungeon[0].length;
        search(0,0,0,0);
        return min+1;
    }
    void search(int curNeed,int hp,int x,int y){
        int tmphp=hp+dungeon[x][y];
        if(tmphp<=0){
            if(curNeed<-tmphp){
                curNeed = -tmphp;
            }
        }
        //结束
        if(x==rows-1&&y==cols-1){
            if(curNeed<this.min) this.min = curNeed;
            return;
        }

        if(curNeed>=this.min) return;

        //向右
        if(y!=cols-1){
            search(curNeed,tmphp,x,y+1);
        }
        //向下
        if(x!=rows-1){
            search(curNeed,tmphp,x+1,y);
        }
    }
}

//倒推dp 题解
class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int n = dungeon.length, m = dungeon[0].length;
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 0; i <= n; ++i) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        dp[n][m - 1] = dp[n - 1][m] = 1;
        for (int i = n - 1; i >= 0; --i) {
            for (int j = m - 1; j >= 0; --j) {
                int minn = Math.min(dp[i + 1][j], dp[i][j + 1]);
                dp[i][j] = Math.max(minn - dungeon[i][j], 1);
            }
        }
        return dp[0][0];
    }
}

